{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 使用区间树完成简易的课表管理系统\n",
    "每一条信息有下面几个参数组成：\n",
    "\n",
    "---------------------------------------------------------------------------\n",
    "\n",
    "action    id    name    start_time     end_time\n",
    "\n",
    "---------------------------------------------------------------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 课表系统的数据结构"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IntervalTree_utils import *\n",
    "\n",
    "class Course(IntervalNode):\n",
    "    def __init__(self):\n",
    "        super().__init__()\n",
    "        self.id = None\n",
    "        self.name = None\n",
    "        \n",
    "class CourseSystem(IntervalTree):\n",
    "    def __init__(self):\n",
    "        super().__init__()\n",
    "        self.root = Course()\n",
    "        self.__nil = self._IntervalTree__nil\n",
    "        self.root.left = self.__nil\n",
    "        self.root.right = self.__nil\n",
    "        \n",
    "    def Insert(self, id_, name, start_time, end_time):    \n",
    "        if self.root.name == None:\n",
    "            self.root.name = name\n",
    "            self.root.id = id_\n",
    "            self.root.val = start_time\n",
    "            self.root.key = start_time\n",
    "            self.root.int = [start_time, end_time]\n",
    "        else:\n",
    "            x = Course()\n",
    "            x.name = name\n",
    "            x.id = id_\n",
    "            x.val = start_time\n",
    "            x.key = start_time\n",
    "            x.int = [start_time, end_time]\n",
    "            flag = self.IntervalInsert(x)\n",
    "            if flag == False:\n",
    "                print('Course id: %s insert Failed because of conflict.' % x.id)\n",
    "                self.Query(x.key, x.int[1], id_=x.id)\n",
    "    \n",
    "    def Delete(self, id_):\n",
    "        # 遍历二叉树查找对应 id\n",
    "        x = self.__search(self.root, id_)\n",
    "        if x != None:\n",
    "            self.IntervalDelete(x.key)\n",
    "    \n",
    "    def Query(self, start, end, id_=None):\n",
    "        q = Course()\n",
    "        q.id = id_\n",
    "        q.int = [start, end]\n",
    "        q.key = start\n",
    "        q.val = start\n",
    "        x = self.IntervalSearch(q)\n",
    "        if x == None:\n",
    "            print('No course.')\n",
    "        else:\n",
    "            print(\n",
    "                'Course id: %s [start, end] = [%s, %s] is conficted with:\\n' % (q.id, start, end),\n",
    "                'id:\\t%s\\n' % x.id,\n",
    "                'name:\\t%s\\n' % x.name,\n",
    "                'start_time:\\t%s\\n' % x.int[0],\n",
    "                'end_time:\\t%s\\n' % x.int[1]\n",
    "            )\n",
    "        return x\n",
    "    \n",
    "    def __search(self, z, id_):\n",
    "        '''\n",
    "        查找对应 id 的节点.\n",
    "        '''\n",
    "        if z == self.__nil:\n",
    "            return None\n",
    "        \n",
    "        if z.id == id_:\n",
    "            return z\n",
    "        \n",
    "        l = self.__search(z.left, id_)\n",
    "        r = self.__search(z.right, id_)\n",
    "        if l == None and r == None:\n",
    "            return None\n",
    "        elif l != None and r == None:\n",
    "            return l\n",
    "        elif l == None and r != None:\n",
    "            return r\n",
    "        # 不可能左右两边有同一门课程"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Course id: 000003 insert Failed because of conflict.\n",
      "Course id: 000003 [start, end] = [16.0, 18.0] is conficted with:\n",
      " id:\t000002\n",
      " name:\tmusic\n",
      " start_time:\t16.0\n",
      " end_time:\t18.0\n",
      "\n",
      "Course id: None [start, end] = [8.0, 18.0] is conficted with:\n",
      " id:\t000002\n",
      " name:\tmusic\n",
      " start_time:\t16.0\n",
      " end_time:\t18.0\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<__main__.Course at 0x1a24546c9e8>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IntervalTree_utils import *\n",
    "T = CourseSystem()\n",
    "T.Insert(id_='000001', name='math', start_time=14.00, end_time = 16.00)\n",
    "T.Insert(id_='000002', name='music', start_time=16.00, end_time = 18.00)\n",
    "T.Delete(id_='000001')\n",
    "T.Insert(id_='000003', name='english', start_time=16.00, end_time = 18.00)\n",
    "T.Query(start=8.00, end=18.00)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "torch",
   "language": "python",
   "name": "torch"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
